~F83. NESTING.

	Let the given polygon  be named Poly; and let  the surrounder
of Poly be  called Exopoly; and assume that Exopoly surrounds several
enclaved polygons called  "endo's", which are  already in the  nested
polygon tree. Also, there are two  kinds of temporary lists named the
PLIST and  the NLIST. There is one PLIST which is initially a list of
all the ENDO polygons on  Exopoly's ENDO ring. Each endo in  turn has
an NLIST  which is initially  empty.  The  subroutine INTREE re-scans
the sky array for the polygon  due east of the uppermost left  vector
of each  endo polygon on  the PLIST, (Exopoly's  ENDO ring).  On such
re-scanning, (on behalf of say an Endo1), there are four cases:

	1. No change; the scan returns Exopoly;
	   which is Endo1's original EXO.
	2. Poly captures Endo1; the scan returns Poly indicating
	   that endo1 has been captured by Poly.
	3. My brothers fate; the scan hits an endo2 which
	   is not on the PLIST; which means that endo2's EXO is valid
	   and is the valid EXO of endo1.
	4. My fate delayed; the scan hits an endo2 which is still
	   on the PLIST; which means that endo2's EXO is not yet
	   valid but when  discovered it will also be Endo1's EXO;
	   so Endo1 is CONS'ed into Endo2's NLIST.

When an endo  polygon's  EXO has  been  re-discovered, then  all  the
polygons on  that endo's NLIST are also  placed into the polygon tree
at that place. All of this link crunching machinery takes half a page
of code and is not frequently executed.




		KRAKAUER'S NESTING ALGORITHM.


~I1973,800;F8- 28 -~
M400;F2
	"The  image  tree is generated one threshold level at a time, starting at the
highest level (branch tips). At each level, the image  is  scanned,  and  the  points
above  the threshold are marked in a scratch array. This scatch array is then scanned
for marked points. When one is found, a contiguity routine is  called,  which  visits
all  marked  points  which can be reached from the start via a connected path.    The
marks are erased by this routine as it goes, and statistics are kept  on  the  region
thus  generated,  such  as the sums of the x and y coordinates of the points, and the
sum of the squares of the x and y coordinates (used  to  compute  the  centerand  the
eccentricity).  A  tree  node is then made up for the region, and the scan for marked
points continues.   A special mark is left in the scratch array for each region. When
this  mark  is  encountered  during the scan at the next level, it is looked up on an
association list. This establishes the link between a region and  the  regions  which
are a subset of it at the previous level - i.e.  between a node and its sub-nodes."

	"The  contiguity  scan  is  the  most  complex  program.  It works by leaving
directional pointers in the scratch array.  These are three-bit codes denoting one of
the  eight  possible  neighboring  points. The contiguity scan is always started at a
point which is on the bottom edge of the region. It traces along  this  edge  to  the
right  by  moving  from one marked point to the next, but always keeping an un-marked
point to the right side. As it goes, it erases the marks, so that for a  region  with
smooth  boundaries, it will follow a spiral path to the center, "eating up" the marks
as it goes, like a lathe with the tool continually advancing into the work."

	"As the contiguity routine scans, it lays down back pointers in  the  scratch
array  which  enable  it  to  retrace  its  path back to the start.  If a dead end is
reached (no more marked neighbors), it traces  back  along  this  path,  looking  for
marked  points  to  the  right.  There can be no marked points on the left side while
backtracking, since this was the right side on the way out,  and  the  outgoing  scan
stayed as far to the right as possible.  If a marked point is found on the backtrace,
it is replaced with a pointer to the adjacent path already traced out, and then a new
path  is  traced as if this were a new starting point. When the backtrace reaches the
original starting point, the contiguity  scan  is  completed.   The  effect  of  this
algorithm  is to construct a tree of pointers in the scratch array, with the starting
point at the root. All points which can be reached via  a  connected  path  from  the
starting point will be a part of this tree."